Computer Graphics ICU

计算机图形学期末笔记整理

Lecture_1_pipeline

Rendering Pipeline

Pixels refers to the dots on the display. A pixel is 2-dimensional, with a (x, y) position and a RGB color value .
A fragment is 3-dimensional, with a (x, y, z) position. The (x, y) are aligned with the 2D pixel-grid. The z value (not grid-aligned) denotes its depth.

main stages:

Vertex Processing: Process and transform individual vertices and normals.
Rasterization: Convert each primitive (connected vertices) into a set of fragments. A fragment can be treated as a pixel in 3D spaces, which is aligned with the pixel grid, with attributes such as position, color, normal and texture.
Fragment Processing: Process individual fragments.
Output Merging: Combine the fragments of all primitives (in 3D space) into 2D color-pixel for the display

Z-Buffer

Lecture_2_transformation

Basic 2-D transformations: refer to my hand-written notes.

Homogenous Coordinates 均质坐标

Add a third coordinate (w-coordinate)

2D point = (𝑥, 𝑦, 1) 𝑇 2D vector = (𝑥, 𝑦, 0)

rotate around a given point c: 先将中心点转移到原点，旋转，转换回去

3D Rotations——Rodrigues’ Rotation Formula：

Viewing and Perspective

viewing 观测 projection 投影（Orthographic 正交）（Perspective 透视）

standard camera space:

How about that we always transform the camera to the origin, up at Y, look at -Z.

for orthographic projection: Looking at / along -Z is making near and far not intuitive (n > f)

how to do perspective projection:

First “squish” the frustum into a cuboid (n -> n, f -> f) (Mpersp->ortho)
Do orthographic projection (Mortho, already known!)

Any point on the near plane will not change.

Any point’s z on the far plane will not change.

What’s next after MVP?

Canonical Cube to Screen.

Lecture_3_rasterization

Aliasing and Antialiasing 走样？失真？

Why triangles?

Most basic polygon - Break up other polygons
Triangles have unique properties
- Guaranteed to be planar 平坦的
- Well-defined interior 内部
- Well-defined method for interpolating values at vertices over triangle (barycentric interpolation) 重心坐标插值

如果我们单纯用采样点判断是否点在三角形内：Jaggies！ 锯齿状！

Sampling artifacts: Jaggies, Moire patterns(摩尔纹)(skip odd rows and columns), wagon wheel illusion

如何 Antialiasing ?

Blurring (Pre-Filtering) Before Sampling 采样前的模糊处理

Note antialiased edges in rasterized triangle where pixel values take intermediate values

为什么采样不足会导致aliasing

filter: Getting rid of certain frequency contents

留下高频：边界留下低频：模糊

原理？Convolution 卷积求平均

Sampling = Repeating Frequency Contents

Antialiasing

how to?

increase sampling rate:

Sampling theorem——The sampling frequency has to be more than twice the maximum frequency of the signal to be sampled

costly! may need very high resolution.

antialiasing: filtering out high frequencies before sampling.
MSAA, multisampling antialiasing

Approximate the effect of the 1-pixel box filter by sampling

multiple locations within a pixel and averaging their values
Super sampling

Take NxN samples in each pixel. Average the NxN samples “inside” each pixel. This is the corresponding signal emitted by the display

Lecture_4_illumination & shading

光照和着色

shading models: To describe how the object’s color should vary based on factors such as surface, orientation, view direction, and light

Gooch Shading Model

Light sources

directional lights 方向光
punctual lights 精确光

point/ omni lights 点/泛光源 spotlights 聚光灯

Transparency

Blinn-Phong Reflectance Model

主要搞三个东西：Specular highlights 镜面高光 Diffuse reflection 漫反射 Ambient lighting 环境光

cosine power plot: increasing p narrows the reflection lobe.

Shading Frequencies

Flat shading: triangle face is flat: one normal vector(not good for smooth surfaces)
Gouraud shading: interpolate colors from vertices across triangle
Phong shading: interpolate normal vectors across each triangle

compute full shading model at each pixel

phone 是最贵的模型(frequency 最大)，blinn-phong 比漫反射贵

Recap of the Graphics Pipeline

Lecture_5_texturing mapping

In computer graphics, texturing is a process that takes a surface and modifies its appearance at each location using some image, function, or other data source.

In order to use textures, three steps: acquisition, texture mapping, texture filtering

Acquisition

texture compositing 纹理合成

Synthesize a large texture from a specific sample. Obviously, this method is very popular with users. Because using this algorithm, the user only needs to provide a small sample of the image。
- pixel-based texture compositing

Texture Mapping

Manually specify texture coordinates:

Assign a texture coordinate to each vertex
Reflects a triangle in image space into object space

Mesh parameterization : Construct a mapping from the 3D model to the plane domain

Conformal parameterization and area retention: Conformal parameterization requires maintaining right angles

Text Filtering

Isotropic filtering 各向同性过滤

Mipmapping: Constructs an image pyramid consisting of a set of prefiltered -and resampled images. These images are samples of the original image at the scales of 1/2, 1/4, 1/8, etc.

problem: over-blur !! 远处过度模糊了
Anisotropic filtering 各向异性过滤

Construct a ripmap by precomputing the filtering of each heterosexuality instead of a mipmap (multi-level texture)

But what happens if the projected square covers ten times as many pixels as the original image contains (called magnifification), or if the projected square covers only a small part of the screen (minifification)?

texels/pixels<1 近处，一个结构包含多个像素 Magnification(blurring)

texels/pixels>1 远处，一个像素包含多个结构 Minification(mipmapping)

Bump Mapping

通过改变表面的法向来改变光照着色的效果，从而实现凹凸贴图。不改变几何

Displacement Mapping

Realistically move surface points with texture maps.

Before visibility can be determined, the geometry must be shifted

Must be done at preprocessing, not hardware rendering

Lecture_6_shadow

Shadow is important: With the hint of the shadow, we can clearly know the position of the ball. Different shadows can correspond to different pellet positions

Hard or soft?

Hard shadow: in a binary state, each point either in the shadow or not. This understanding corresponds to hard shadows, which are produced by point lights.

Hard shadows can give the image a rather unreal feeling.
however, under finite extent lights (usually area lights), it is often difficult to determine the umbra and penumbra regions, because this means that fan 1 needs to solve the visible relationships in 3D space. This is a very difficult question.

Planar Shadow

When the shadow of an object is projected onto a flat surface, a planar shadow is produced, and a planar shadow is one of the simplest kinds of shadows.

In the shadow projection method, objects in three-dimensional space need to be drawn twice to achieve a shadow effect. Specifically, a matrix is used to project points on the surface of the occlusion onto the plane on which the shadow needs to be calculated

if on surfaces?

To extend the calculation of the previous planar shadows to curved surfaces, a natural idea is to use the shadow image as the projective texture.

Imagine using the light source as the viewpoint: the area seen from the light source is drawn; The area that cannot be seen from the light source is the shadow

disadvantages: Objects cannot cast shadows onto themselves

Shadow rendering algorithm

Shadow volume algorithm

First, imagine a point and a triangle in three-dimensional space, connect the points to the three vertices of the triangle and extend them, resulting in a triangular pyramid derived to infinity

Think of a point as a point light source, then any part of any object, as long as the top of the triangular pyramid is cut out in the following image, it belongs to the shadow area

Improve: using template caching(Stencil Buffer)

The stencil buffer can store an integer value for each pixel; It differs from the depth cache z-buffer only in that the z-buffer stores a depth value in real terms.

Advantages:
- First, it can be implemented using general-purpose graphics hardware, but only requires a stencil buffer.
- Second, since it is not an image-based method (unlike the shadow map algorithm described below), the shadow volume calculation does not create all kinds of problems caused by sampling and resolution, so that correct and sharp shadows can be generated anywhere.
Inadequacy:

Since the number of polygon patches of the shadow volume is usually large, and it will cover a large number of pixels, this greatly affects the speed of the algorithm operation and the rasterization process, making the drawing efficiency low.
Shadow Map

Using the depth cache z-buffer, the distance from the light source to the nearest point in either direction can be obtained and stored in the form of an image, as shown in the figure:

Advantage:
- Most hardware can directly support the shadow map algorithm for drawing shadow effects for any scene.
- The shadow map algorithm is very fast, and the cost of building a shadow map is proportional to the number of rendered primitives to be drawn; When using a shadow plot for shadow drawing for any viewpoint, each pixel requires only one additional query for the shadow map and a comparison of distances, which can be done in a constant time.
Deficiencies:

Its drawing quality is affected by the resolution of the shadow map and the accuracy of the z-buffer’s value.

Problems with the shadow graph algorithm:

When the epsilon value used in distance comparison is too small, it may produce a moire pattern similar to the one below on the surface of the object
When the epsilon value used for distance comparison is too large, the shadow shape is deformed and a feeling similar to the floating of an object is created.

变形，影子浮动

Lecture_7_geometry

two categories: Implicit and explicit

Implicit: Level sets, Algebraic surface, Distance functions

Explicit: Point cloud, Polygon mesh, Subdivision, NURBS

Implicit

Based on classifying points: Points satisfy some specified relationship
Explicit

All points are given directly or via parameter mapping

Implicit Representations

Constructive Solid Geometry(Implicit)

Distance functions(Implicit)

Instead of Booleans, gradually blend surfaces together using Distance functions:

giving minimum distance (could be signed distance) from anywhere to object.

Explicit Representations

Point cloud

Easiest representation: list of points (x,y,z)

Easily represent any kind of geometry

Often converted into polygon mesh

Difficult to draw in undersampled regions
Polygon Mesh 多边形网格

Store vertices & polygons (often triangles or quads)

Easier to do processing / simulation, adaptive sampling

More complicated data structures

Perhaps most common representation in graphics

Bezier Curves 贝塞尔曲线

Higher-Order Bezier Curves? n=10 hard to control!

Instead, chain many low-order Bezier curve.

贝塞尔曲面：用曲线生成

Lecture_8_geometry_cont

Local Mesh Operations

Global Mesh Operations

Mesh subdivision(upsampling)
- Loop subdivision: create more triangles and tune their positions.
- Caimull-Clark Subdivision
Mesh Simplification

reduce number of mesh elements while maintaining overall shape

Collapse an edge: 把三角形坍缩成一个点

how much does it cost to collapse an edge?

compute edge midpoint, measure quadric error

choose point that minimize the quadric error

Lecture_9_raytracing

Rasterization couldn’t handle global effect well, and especially when the light bounces more than once.

Ray tracing is accurate, but is very slow.

Rasterization: real time raytracing: offline

basic:

pinhole camera model

Recursive Ray Tracing

递归地跟踪射线，直到到达非镜面曲面或者递归终止深度。

Ray Intersection

如何判定相交？

首先计算出光线和三角形所在平面的交点，然后判断是否交点在三角形内。

Barycentric coordinates 重心坐标

With polygon? 与多边形相交？

A point on the plane is located inside a polygon, if and only if any ray from this point has an odd number of intersections with the boundary of the polygon, so the intersection detection algorithm based on this theorem is also called the parity detection algorithm.

With Sphere?

Mathematical solutions:

There is a lot of room for improvement and speedup of the previous algebraic methods: for example, we don’t actually need to compute the second intersection that is stalled.
Geometry solutions

With box!

Accelerating

Uniform Spatial Partitions(Grid)

find bounding box->create grid->store each object in overlapping cells->test intersection

one cell: no speed up. too many cells: inefficiency due to extraneous grid traversal

Spatial Partitions

K-D Tree

每次换一个轴进行partion，遍历的时候沿着树遍历判断intersection
Bounding Volume Hierarchy

better? choose the longest axis in node
Comparision

Lecture_12_raytracing_cont

Radiometry

the basics of Path Tracing

Radient Intensity

Definition: The radiant (luminous) intensity is the power per unit solid angle (立体角) emitted by a point light source.

单位立体角的功率

Solid angle: ratio of subtended area on sphere to radius squared
Irradiance

Definition: The irradiance is the power per (perpendicular/ projected) unit area incident on a surface point.

输入到曲面点上的每个单位面积的功率。
Radiance

Definition: The radiance (luminance) is the power emitted, reflected, transmitted or received by a surface, per unit solid angle, per projected unit area.

每单位立体角、单位投影面积的表面发射反射传输或接收的功率

Definition: power per unit solid angle per projected unit area.
Incident Radiance

Incident radiance is the irradiance per unit solid angle arriving at the surface.
Exiting Radiance

Exiting surface radiance is the intensity per unit projected area leaving the surface.